EPO ist als allgemeines Parameter-Optimierungsprogramm anpaßbar an fast beliebige Problemstellungen. Es arbeitet auf Basis eines naturanalogen Algorithmus und benötigt keinen Einblick in die mathematischen Zusammenhänge des zu optimierenden Systems. Stattdessen wird implizit eine eigenständige Modellierung im Verlaufe eines Optimierungslaufes aufgebaut, indem aus Erfolgen und Mißerfolgen von Tastschritten nach dem Modell der biologischen Evolution gelernt wird. Deshalb kann EPO insbesondere mit eigenständigen Simulationsprogrammen zusammenarbeiten, die zunächst überhaupt nicht auf eine Optimierungsproblematik hin erstellt wurden.
Der evolutionäre Grundalgorithmus erhöht die Stabilität und Konvergenzsicherheit gegenüber deterministisch arbeitenden Optimierungssystemen erheblich. EPO ist daher insbesondere bei schwierigen Fragestellung einsetzbar.
In der vorliegenden Shareware-Version können bis zu fünf Parameter gleichzeitig bearbeitet werden, während die Vollversion nur durch den Hauptspeicherplatz beschränkt wird. Spezialisierte Versionen, die nicht durch ein allgemeines Schema abgedeckt werden können, sind auf Nachfrage erstellbar.
EPO setzt als Baukastensystem zu seiner Anwendung Programmierkenntnisse bei der Anbindung des externen oder neu zu programmierenden Simulators voraus. Beigelegte Programmschablonen (C-Quelltext) vereinfachen diese Aufgabe erheblich, so daß sich der Nutzer auf den wesentlichen Teil seiner Arbeit, die korrekte Simulation des zu optimierenden Systems, beschränken kann.
EPO setzt ein multitasking-fähiges Betriebssystem voraus. In der vorliegenden Version ist es für OS/2-PCs gedacht; eine Unix-Version wird momentan auf möglichst viele Plattformen portiert. (Nein, eine Portierung auf DOS ist {\em nicht} vorgesehen!)
\section{Einleitung: Naturanaloges Optimieren in der Technik}
\subsection{Optimierungsverfahren}
Damit ein Ding oder eine Methode in der Praxis eingesetzt oder angewendet werden kann, muß es den Zweck, der seiner Entwicklung zugrunde lag, in einem hinreichenden Maße erfüllen. Wenn auch oft bei der Einführung neuer Verfahren oder Geräte deren Funktion noch nicht ganz ausgereift ist, wird sie doch im Laufe der Weiterentwicklung immer weiter verbessert, nicht zuletzt durch den Konkurrenzdruck alternativer Lösungsansätze --- wobei wir schon fast bei der zugrundeliegenden Idee des hier beschriebenen Programmsystems wären, wenn auch in einem etwas anderen Zusammenhang.
Diese Verbesserung, ab jetzt Optimierung genannt, läßt sich mittels verschiedener Verfahren erreichen:
%
\begin{itemize}
\item Man durchschaut als Entwickler eines neuen Verfahrens oder Gerätes die zugrundeliegenden Zusammenhänge und wählt kurz und genial die beste Vorgehensweise zum Erreichen des gewünschten Ziels. Diese Art von Optimierung wird zwar in der Regel angestrebt, ist in der Praxis aber eher selten realisierbar.
\item Man entwickelt zunächst einen Prototyp des Gerätes, testet diesen und überlegt sich eine Reihe von Detailverbesserungen, die dann schrittweise am Prototyp ausprobiert werden. Dies dürfte einer der meistgenutzten Vorgehensweisen bei einfachen und billigen Produkten sein.
\item Man simuliert das Verhalten eines Systems rechnerisch und kann aufgrund der bekannten mathematischen Zusammenhänge zwischen den das Verhalten bestimmenden Variablen mathematisch-analytisch die optimale Parameterkonstellation ermitteln. Einfachste Beispiele hierfür sind die berühmt-berüchtigten Minimum-Maximum-Aufgaben der Mathematikleistungskurse im Gymnasium.
\item Eine analytische Lösung ist trotz mathematischer Modellierung nicht mehr möglich, vielleicht, weil die gesuchte Zielfunktion (die zu optimierende Größe) nicht mehr als geschlossener Ausdruck angegeben werden kann. Bei dieser in vielen praktischen Fällen auftretenden Situation ist man auf Suchverfahren angewiesen ist. Üblicherweise werden diese aus der analytischen Extremwertsuche abgeleitet. Solche Verfahren werden in vielen Standardwerken des Operations Research und der allgemeinen Optimierungsmethodik diskutiert, z.B. auch in~\cite{ HoffHof} und~\cite{ Zach}.
\item Man verzichtet auf die analytische Behandlung der Extremwertsuche und setzt Zufallsverfahren ein, um sich dem Optimum zu nähern. Dies kann insbesondere dann interessant sein, wenn sich die interessierende Eigenschaft des zu optimierenden Systems verschiedene relativ gute Parameterkonstellationen besitzt (Suboptima) oder allgemein in komplizierter Form von den Parametern abhängen. In solchen Fällen laufen die aus der Analysis abgeleiteten Optimierungsverfahren häufig in die Irre und konvergieren nicht am Optimum, wie Praktiker sicher aus eigener Erfahrung bestätigen können.\\
Eine besondere Klasse von Verfahren kopiert die Vorgehensweisen der Natur und wird daher auch ``naturanaloge Optimierungsverfahren'' genannt. Hier finden sich verschiedene Ideen umgesetzt --- angefangen vom ``simulierten Ausglühen'', einem aus der Physik der Erstarrungsphänomene abgeleiteten Paradigma~\cite{ Otto:SimAn}, bis hin zu den aus der Biologie entlehnten, sich an die Evolutionstheorie anlehnenden Verfahren~\cite{ Rieck:ModellNatur, Schwef:Opti}.
\end{itemize}
Zur letzteren Klasse der Optimierungsverfahren gehört auch der Algorithmus, der dem vorliegenden Optimierungsprogrammsystem zugrunde liegt und allgemein als Evolutionsstrategie bezeichnet wird. Er wird insbesondere durch die beiden Begriffe ``(zufällige) Mutation'' und ``(deterministische) Selektion'' beherrscht.
Er setzt natürlich voraus, daß das zu bearbeitende System in einer rechnersimulierbaren Form vorliegt. Es wurden jedoch auch schon Fälle in der Literatur diskutiert, in denen er in rein experimentell-praktisch durchgeführten Optimierungen eingesetzt wurde~\cite{ Rechen:Evolut}.
\subsection{Grundlegende Ideen des naturanalogen Optimierens}
Bevor weiter unten die Systembestandteile und die praktische Arbeit mit EPO beschrieben werden, möchte ich kurz auf die Ideen der naturanalogen Optimierungsverfahren eingehen, da sie sich grundlegend von denen herkömmlicher Verfahren unterscheiden.
Die biologischen Organismen haben sich zweifellos in faszinierender Weise im Laufe der Jahrmillionen von einfachsten Urformen zu fast unvorstellbarer Komplexität entwickelt. Trotz dieses enormen Komplexitätszuwachses hat die Funktionalität in diesem Entwicklungsprozeß stetig zugenommen --- fast im Gegensatz zu technischen Systemen, die bei wachsendem Komplexitätsgrad meist zunehmend fehleranfälliger werden%
\footnote{Jedem Leser dürften hinlänglich Beispiele aus dem eigenen Umfeld
bekannt sein. \yeah}. %
Eine von naturwissenschaftlich-technischen Lösungsansätzen ausgehende Erklärungsweise steht demnach vor einem zunächst nicht auflösbaren Widerspruch.
Die Komplexität der biologischen Organismen hat viele dazu geführt, die Welt als durch ein höheres Wesen geschöpft zu sehen. In der Tat läßt sich beispielsweise durch eine rein kombinatorische Rechnung nachweisen, daß die Wahrscheinlichkeit, das menschliche Erbmaterial in Form der Desoxyribonukle\"insäuresequenzen durch reinen Zufall zu erzeugen, in naturwissenschaftlichen Maßstäben identisch null ist%
\footnote{Auf die Angabe einer ``exakten'' Zahl und eine mathematische Herleitung wird verzichtet, da sie im Zusammenhang dieser Arbeit uninteressant und in vielen biologischen und auch populärwissenschaftlichen Veröffentlichungen zu finden ist.}%
. Diese Betrachtungsweise ist jedoch nicht der Sache angemessen. Aus der großen Zahl unterschiedlicher Erbmaterialien ist zu erkennen, daß nicht nur genaue eine Sequenz die Ausprägung brauchbarer Eigenschaften kodiert, sondern auch Variationen möglich sind.
Weiterhin hat sich seit ihrer ersten Formulierung durch Darwin die Vorstellung einer Abstammungslehre, bedingt durch den Vorgang der Evolution, in der Biologie allgemein durchgesetzt. Ihre Richtigkeit wird heute nicht mehr in Zweifel gestellt, da im Laufe der Zeit überzeugende Belege für ihre Richtigkeit gefunden wurden. In Verbindung mit der Entwicklungsphysiologie und der Genetik entstand in den letzten Jahrzehnten ein weitgehend lückenloses Erklärungsschema für die Vielfältigkeit unserer heutigen Welt~\cite{ Hoppe:Biophysik}.
Die grundlegende Fortentwicklung der biologischen Systeme geschieht demnach durch die Evolution, also durch das `Ausprobieren' neuer Varianten von Lebewesen, die sich meist nur in geringen Details von ihren Vorfahren unterscheiden. Da diese in unmittelbarer Konkurrenz zu den vorhandenen Ausführungen der gleichen Spezies und den anderen Lebewesen stehen, sorgt eine natürliche Auslese (letztlich: Unterschiede in der Wahrscheinlichkeit, überlebensfähige Nachkommen in der Welt zu etablieren) dafür, daß auf lange Sicht die jeweils bessere Ausprägung einer speziellen Eigenschaft erhalten wird.
Darwin und seine unmittelbaren Nachfolger standen vor dem Problem, die von Generation zu Generation erfolgenden Modifikationen erklären zu müssen. Der Mechanismus sowohl der Übertragung der unveränderten wie auch der modifizierten Information von den Eltern auf ihre Nachkommen konnte erst seit der Klärung des Kodierungsverfahrens vererbungsdeterminierter Eigenschaften durch Watson, Crick und Nachfolger~\cite{ Hoppe:Biophysik} schlüssig belegt werden.
Seit diesen grundlegenden Untersuchungen ist bekannt, daß sich wesentliche Teile der Evolution durch die Entwicklung und Weitergabe einer stetig komplizierter und umfangreicher werdenden Informationssequenz verstehen lassen. Damit lassen sich aber gewisse Parallelen zu mathematisch-kombinatorischen Problemen erkennen, die ebenfalls durch evolutionsstrategische Ansätze lösbar wurden, obwohl nachweisbar ähnliche Wahrscheinlichkeiten, die jeweiligen Lösungen `durch Zufall' zu finden, existierten wie in der oben angesprochen biologischen Problemstellung. Beispiele sind in großer Zahl in der Literatur zu finden, z.B.\ das ``Problem des Handlungsreisenden''~\cite{ Muehle:EvoAlgs}.
Die Idee der Höherentwicklung durch Evolution ausgeführter Systeme wird durch entsprechende Algorithmen auf technische Systeme übertragen. Dieser Weg wurde in Deutschland erstmals Ende der sechziger Jahre von Rechenberg et.~al~\cite{ Rechen:Evolut}. beschritten. Insbesondere Schwefel und Mitarbeiter~\cite{ Kursaw:Vektor, Handelsreis, Schwef:Opti, Schwef:DirectSearch, Schw88, PPSN:1990} erweiterten den grundlegenden Algorithmus und entwickelten die ursprünglichen Verfahren weiter.
\subsection{Grundlegende algorithmische Struktur der Evolutionsstrategie}
Entsprechend dem Vorbild der Natur betrachten Evolutionsverfahren nicht ein einzelnes zu optimierendes Gerät/Verfahren, sondern üblicherweise eine {\em Population\/} aus diesen. Eine solche Population wird aus {\em Individuen}, also ausgeführten Beispielen des Gerätes/Verfahrens zusammengestellt, die sich in ihrem Genom, also den das Verhalten bestimmenden ``Erbanlagen'' voneinander unterscheiden.
Ein Beispiel mag diese vielleicht befremdlich anmutende Begriffsbildung erläutern:
Will ich etwa die Energiekosten eines Hauses minimieren, kommen als (die Kosten) beeinflussende und (bei der Auslegung) beeinflußbare Parameter unter anderen Mauerstärke, Mauermaterial, Fensterverglasung, Heizungssystemauslegung, Fugendichtigkeit und Dachmaterialwahl in Betracht. Diese sechs Parameter stellen für ein einzelnes Baukonzept, also mein Individuum, die Erbanlagen dar und beeinflussen den hieraus resultierenden Zielfunktionswert ``Energiekosten''%
\footnote{Man beachte, daß ich hier bewußt nicht den Energie-{\em verbrauch\/} des Hauses als Zielfunktion verwendet habe: Das Ergebnis einer Optimierung wäre trivial, es ergäbe sich nämlich jeweils das bestmöglich dämmende Material. Durch die Berücksichtigung des Kostenaspekts wird sich aber ein praktisch verwertbares, nicht-triviales Ergebnis einstellen: Es bringt bei guter Dämmung praktisch keine Energieeinsparung mehr, die Dämmung weiter zu verbessern, kostet aber eine Menge Geld.} .%
In der Population sind nun unterschiedliche Individuen, d.h.\ unterschiedliche Zusammenstellungen der sechs Parameter vertreten, die hierdurch auch unterschiedliche Zielfunktionswerte besitzen. Als Analogie zu einem Tastschritt der deterministischen Optimierungsverfahren tritt bei den evolutionsstrategischen Verfahren die Bildung einer neuen {\em Generation.\/} Hierzu werden die (hinsichtlich Zielfunktionswert $Z$) $n$ besten Individuen ausgewählt und aus ihnen $m$ Nachkommen durch ein dem biologischen Rekombinationsprozeß nachgebildetes Verfahren und zusätzlicher zufälliger Variation der Parametereinstellungen erzeugt.
Je nach gewählter Strategievariante werden entweder die Eltern vollständig verworfen (sog.\ Kommastrategie~\cite{ Schwef:Opti}) und bei der Auswahl der Eltern für die darauffolgende Generation ausschließlich die neuen Nachkommen berücksichtigt, oder die Eltern bilden mit den Nachkommen eine Gesamtpopulation, aus der nach Sortierung die neuen Eltern gewonnen werden(sog.\ Plusstrategie).
Wenn auch die Konvergenzqualität der Kommastrategie auf den ersten Blick fraglich erscheint --- werden doch einmal erreichte Optimierungserfolge u.U. durch Nicht-Weitergabe an die Nachkommen wieder Zunichte gemacht --- hat sie sich insbesondere in Verbindung mit der Selbstadaption der Suchschrittweiten als die bessere herausgestellt. In EPO ist daher derzeit nur diese Kommastrategie implementiert.
\bigskip
Ein Hinweis zum Schluß dieser Einführung: Auch EPO kann nicht zaubern und ist keine Wunderwaffe bei Optimierungsproblemen! Es wird Fälle geben, wo auch EPO nicht zum bestmöglichen Ergebnis führt oder eine Optimierung einfach zu viel Zeit beansprucht, bevor sie zu einem sinnvollen Ergebnis führt.
Dies ist dann aber nicht ein Fehler des Programms oder des Algorithmus, sondern einfach in der Tücke des Objekts bedingt. Und praktische Optimierungsprobleme sind oft tückisch $\ldots$
Es wird auch manche Fälle geben, in denen ein deterministischer Optimierer mit seiner gezielten Suche nach der besten Fortschrittsrichtung im Laufe einer Problembearbeitung schneller zu einem guten Ergebnis kommen wird. In solchen Fällen möge man diesen Methoden den Vorzug geben. EPO wird aber gerade dort interessant, wo diese deterministischen Verfahren bekanntermaßen versagen.
Insbesondere, wenn auf einen schon existierenden, in sich geschlossenen Simulator zurückgegriffen werden muß, damit also die innere Modellbildung der Simulation dem Optimierer zwangsläufig verborgen bleibt, greift die Methodik der evolutionären Optimierung besonders gut. Und diese Fälle dürften gar nicht so selten sein!
\subsection{Umsetzung der Evolutionsstrategie in ein Programmsystem}
Die in den Individuen verwalteten ``Erbanlagen'' --- also die momentanen Parametereinstelldaten --- stellen die gesamte Information dar, die zur Qualitätsbestimmung eines Gerätes/Verfahrens erforderlich ist. Sie wird über den oben erläuterten Vererbungsmechanismus an die Nachkommen in modifizierter Form weitergegeben.
Hierzu werden sie vom Hauptmodul des Systems, dem sogenannten ``Optimierer'' anfangs aus einem Konfigurationsfile gelesen und während des Optimierungslaufs verwaltet und bearbeitet. Der Optimierer ist auch für die Interaktion mit dem Benutzer zuständig und erstellt die Ergebnis- bzw.\ Fortschritttsreports.
Die genaue Strategie des evolutionären Algorithmus kann durch Festlegung verschiedener Steuerparameter ebenfalls per Konfigurationsfile beeinflußt werden und so auf unterschiedliche Probleme (insbesondere hinsichtlich der Abwägung zwischen Optimierungs-Fortschrittgeschwindigkeit und der Konvergenzsicherheit bei multimodalen Problemstellungen) angepaßt werden.
\bigskip
Die Bestimmung des Zielfunktionswertes bei einer gegebenen Parameterkonstellation hat mit dem evolutionsstrategischen Teil des System nichts zu tun. Daher wurde der ``Simulator''-Teil komplett von diesem getrennt. Er kommuniziert mit dem Optimierer lediglich durch Übergabe von Daten- und Nachrichtenfiles.
Je nach konkreter Aufgabenstellung bieten sich verschiedene Wege zur Einbindung des Simulators an:
%
\begin{itemize}
\item Der Simulator muß als Programm neu erstellt werden:\\
Für diesen Fall ist eine Programmschablone im Paket enthalten, das die gesamte Kommunikation mit dem Optimierer abwickelt und einen Unterprogrammrumpf namens \verb+rechne()+ bereitstellt, in dem die zu formulierende Simulation eingebracht werden kann. Der Zugriff auf alle Parameterwerte und deren Bezeichnungen ist hierbei gegeben.
\item Es existiert ein fertiger Simulator für das zu optimierende System:\\
Hier sind üblicherweise Aufrufkonventionen des Simulatorprogramms zu beachten (z.B. Übergabe von speziell aufbereiteten Datenfiles, Übergaben per Kommandozeile, usw.). Auch für diesen Fall liegt eine Programmschablone bei die für den jeweiligen Anwendungsfall recht einfach angepaßt werden kann. Wiederum übernimmt die Schablone die Kommunikation mit dem Optimierungsteil und stellt die aktuellen Parametereinstellungen bereit. Die Ansteuerung des externen Simulators muß der interessierte Anwender dann noch im Unterprogramm \verb+rufe()+ hinzufügen.
\end{itemize}
Das Arbeiten mit diesen Systembestandteilen wird weiter unten, in Abschnitt~\ref{Arbeitsweise} und~\ref{Praxis} noch genauer erläutert.
\section{Systembestandteile}
Wenn auch verschiedentlich von Anwendungen der naturanalogen Verfahren bei technischen Fragestellungen berichtet wird~\cite{ Doerin:Filter, Muelle:EvoBeisp, Schmie:Mikrowelle}, ist mir bisher kein Anwendersystem bekannt, das sich relativ einfach und flexibel an konkret gegebene Problemstellungen anpassen läßt. Diesem Mißstand soll mit EPO als modularem Optimierungssystem auf Basis der Evolutionsstrategie begegnet werden.
Im Sinne einer einfachen Anpaßbarkeit an immer neue Problemstellungen wurde EPO modular aufgebaut. In der Shareware-Version sind alle Module der Vollversion enthalten, damit Sie die Flexibilität des Systems ausprobieren und abschätzen können.
Das Programm ist so angelegt, daß es auf beliebige rechnersimulierbare Probleme anwendbar ist, solange das Betriebssystem des Zielrechners ein gleichzeitiges Abarbeiten von Simulations- und Optimierungsprogramm erlaubt. Auf der PC-Schiene bietet sich hierzu OS/2 als Betriebssystem an, jedoch ist das Programm praktisch ohne Änderung auf Unixmaschinen lauffähig --- natürlich in einer umkompilierten Version! Ich bin zur Zeit dabei, EPO auf unterschiedlichste Unix-Plattformen zu portieren%
\footnote{Entsprechend sollten diese im Laufe der Zeit auf entsprechenden FTP-Servern auftauchen. Bei unmittelbarem Bedarf auf einer derzeit nicht unterstützten Plattform bitte ich darum, mich unmittelbar anzusprechen --- e-mail-Adresse siehe oben!}.
Zum Einstieg in die praktische Optimierungsarbeit sind dem Paket Problembeispiele beigelegt, die als Funktionstest des installierten Systems verstanden werden können.In Abschnitt~\ref{Praxis} wird noch ausführlich erklärt, wie eigene Problemstellungen mit diesem Programmsystem bearbeitet werden können. Dies setzt eine gewisse Programmiererfahrung voraus, weil eine definierte Schnittstelle zwischen dem Optimierungsmodul und dem das Problem beschreibenden Simulator eingehalten werden muß. Diese ist aber so einfach gehalten, daß keine allzugroßen Schwierigkeiten bei der Implementation auftreten dürften.
\bigskip
Kern des Systems ist das Programm SHOPTI.EXE%
\footnote{SHOPTI.EXE ist der Name der OS/2-Version. Entsprechende Unix-Executables sind entsprechend SHOPTI genannt. Im folgenden gilt für diese Module das gleiche, was für die OS/2-Version gesagt wird, es sei denn, es wird explizit auf Unterschiede hingewiesen}, %
das durch einen RENAME-Aufruf aus der Datei SHOPTI.BIN erzeugt wird.
Ich gebe zu, das diese Vorgehensweise vielleicht ein wenig hinterhältig ist. Ich möchte aber um Verständnis für diesen Weg bitten, weil ich nicht glaube, daß irgendjemand ohne Lesen dieser Anleitung mit dem Programmsystem irgendetwas anfangen kann. Und bevor sinn- und kontextlos eine .EXE-Version aufgerufen wird, wollte ich den potentiellen Benutzer auf diese Weise an diesen Anleitungstext heranführen.
SHOPTI.EXE ist das eigentliche Optimierungsmodul, das die gesamte Steuerung übernimmt und den Ergebnisreport generiert. Es enthält den wesentlichen, evolutionsstrategischen Algorithmus.
In der Shareware-Version erlaubt EPO eine Maximalzahl von 5 Variablen. Dies ist eine Einschränkung der Funktionalität --- gewiß! Aber bevor nun der Ruf ``{\em Crippleware!}'' erschallt: Es gibt sehr viele Optimierungsprobleme, die trotz geringer zu bearbeitender Parameterzahl für deterministische Optimierer eine harte Nuß darstellen und die mit EPO gelöst werden können! Außerdem möchte ich am Einsatz von EPO bei größeren Problemen auch gerne etwas verdienen. Zum Test der Möglichkeiten und der Funktionsweise wird die vorliegende Version auf jeden Fall ausreichen.
\bigskip
Das Programm SIMU.EXE ist gleichermaßen aus der Datei SIMU.BIN zu erzeugen. Es bildet den Gegenpart zum Optimierungsmodul SHOPTI.EXE und ist ein ausgeführter Simulatorkern für ein Musterproblem. Als Beispiel wurde die Suche nach dem Minimalwert einer multidimensionalen quadratischen Funktion eingebaut.
Der Quelltext zu diesem Modul ist ebenfalls beigelegt und unter SIMU.C zu finden. Darin besteht die Möglichkeit, eine eigene Problemstellung in Form eines C-Unterprogramms im Austausch gegen das Beispiel zu formulieren, ohne sich um die Übergabe der Parameter- und Ergebnisdatei an das Optimierungsmodul kümmern zu müssen. Der Zugriff auf die Parameter-Datenstrukturen wird anhand des Beispiels vorführt und sollte beim Umschreiben auf eigene Zielfunktionen kein Problem darstellen.
\bigskip
Zur Ansteuerung komplett unabhängiger, eigenständiger Simulatorprogramme sind dessen Eigenarten zu berücksichtigen, insbesondere bezüglich der Aufbereitung der zu übergebenden Parameter. Grundsätzlich ist dies auch über eine entsprechende Modifikation von SIMU.C zu erreichen. Ich möchte Ihnen das Leben jedoch noch etwas einfacher machen und stelle hierzu eine weitere Schablone zur Verfügung: TRANS.C bzw.\ als fertiges Kompilat TRANS.EXE, das auch wieder durch ein Rename aus TRANS.BIN zu erzeugen ist.
Es steuert in der vorliegenden Form den ``Simulator'' GAUSSFIT.EXE (ja, sie haben es schon erraten$\ldots$) an, der die bezogene Fehlerquadratsumme einer gefitteten Gaußglockenfunktion an eine Meßdatenschar berechnet. Hierzu sind GAUSSFIT.EXE fünf Kommandozeilen-Parameter beim Aufruf zu übergeben:
%
\begin{enumerate}
\item Der Name einer Datei, in der die Meßpunkteschar in der Form \{x-Wert, y-Wert\} jeweils in einer Zeile beschrieben ist (Maximalzahl 99 Meßpunkte). Sie finden eine solche Meßdaten-Beispieldatei unter dem Namen REIN.
\item Die Höhe der vorgeschlagenen Fit-Gaußglocke.
\item Der Mittenwert der vorgeschlagenen Fit-Gaußglocke.
\item Die Standardabweichung der vorgeschlagenen Fit-Gaußglocke.
\item Der Name einer Ausgabedatei, in der GAUSSFIT.EXE (unter anderem) die berechnete Fehlerquadratsumme ablegt.
\end{enumerate}
Für diesen vielleicht etwas exotisch anmutenden Programmaufruf stellt nun das beigelegte TRANS.* die Anpassung der Durchrechen-Anforderung des Optimierers dar, indem die erforderlichen Parameter aus dem vom Optimierer geschriebenen Übergabefile entnommen werden, und mit den (den Optimierer nicht interessierenden) Details zu einem Simulatoraufruf zusammengestellt werden. Schließlich wird nach fertiger Bearbeitung des eigentlichen Simulatorlaufs die Rückgabedatei nach der interessierenden Fehlerquadratsumme durchsucht und diese in die an den Optimierer zu verschickende Datenstruktur übertragen.
\bigskip
Des weiteren sind Steuerdateien vorhanden: STRATEG.DAT und CONDITIO.DAT
Deren Bedeutung wird weiter unten ausführlich beschrieben.
Da das Programmsystem mit dem EMX-Compiler erstellt wurde, erfordert es EMX.DLL im Libpath. Auch diese Datei ist im Paket enthalten, wenn auch die meisten Anwender bereits eine Version haben sollten.
Bei Produktionläufen des Optimierungssytems werden noch weitere Dateien erzeugt, deren Bedeutung und Namen weiter unten diskutiert werden. Sie sind in der Regel nicht umfangreich (typischerweise Temporärdateien $<$ 2 kB, Ergebnisdateien $<$ 200 kB) und sollten die Plattenkapazität wohl nicht vor Probleme stellen.
\section{Kurzeinführung in die Arbeitsweise}
\label{Arbeitsweise}
\subsection{Allgemeiner Ablauf eines Optimierungslaufs}
Das Vorgehen bei der Bearbeitung eines Optimierungsproblems ist grundsätzlich immer gleich. Zunächst muß das Simulatormodul über eine Übergabeschnittstelle an das Optimierungsmodul angeschlossen werden, z.B.\ in Form einer direkten Formulierung des Simulationsteils im Unterprogramm \verb+rechne()+ des beigelegten SIMU.C
Steht bereits ein fertiger Simulator zur Verfügung, der sich durch ein Kommando starten läßt und dann ohne interaktive Eingriffe bis zu einem Endergebnis durchläuft, muß dieser durch ein die Parameterübergabe aufbereitendes Mittlerprogramm angesprochen werden. Hierzu kann TRANS.C als Schablone dienen.
Auch die Extraktion der Rückgabewerte und ggf.\ der daraus zu ermittelnde, eigentliche Zielfunktionswert sind vom Mittlermodul zu leisten, das hierzu auf das Erscheinen des Simulator-Ergebnisfiles warten muß. Auch diese Funktionalität ist in TRANS.C bereits vorgesehen.
Schließlich sind die Randbedingungs- und die Strategieparameter-Datei dem Probem anzupassen. Dies ist ausführlich in den nachfolgenden Kapiteln geschildert.
\bigskip
Nachdem diese Vorbereitungen getroffen sind, wird der Optimierer durch Anklicken oder Kommandozeilen-Aufruf gestartet. Er meldet sich mit einer Einschaltmeldung und ruft seinerseits den (im Strategiefile angegebenen) gewünschten Simulator als eigenständig laufenden Prozeß auf. Auch der Simulator gibt in seinem Fenster (ggf.\ nach vorne holen!) eine Einschaltmeldung aus und kann für Kontrollausgabezwecke nach Einbau entsprechender Ausgabetexte zur Sichtkontrolle dienen.
Insbesondere der Optimierer gibt durch eine Reihe von Kontrollausgaben an, ob er die Startdateien korrekt eingelesen hat. Im Lauf der Optimierung werden pro Generation die gewünschte Anzahl von Besten aus der Bestenliste angezeigt. Daran ist der Fortschritt der Optimierung unmittelbar zu erkennen.
Zwischen Optimierer und Simulator werden ständig Dateien transferiert --- jeweils eine Daten-Datei (O2S.DAT bzw. S2O.DAT, je nach Richtung) und eine Flag-Datei (*.MSG), die sicherstellt, daß das wartende Programm erst auf die Datendatei zugreift, wenn sie fertig geschrieben ist%
\footnote{Leider scheint unter den Multitasking-Betriebssystemen OS/2 und Unix unter gewissen Umständen das Schließen einer Datei druch den schreibenden Prozeß nicht immer mit deren Verfügbarkeit für einen Leseprozeß einherzugehen, wie sich insbesondere bei größeren Transferdateien gezeigt hat. Daher wurde gegenüber EPO 0.1 eine Validitätsprüfung eingebaut, die adaptiv arbeitet und jeweils die minimal erforderliche Verzögerungszeit für störungsfreie Interaktion von Optimierer und Simulator einstellt.}. %
Die Flag-Dateien haben keinen Inhalt, nur ihre Existenz ist von Bedeutung.
\bigskip
Der Optimierer kann interaktiv angehalten werden, indem bei aktivem Optimiererfenster die Taste ``q'' gedrückt wird. Diese Tastatureingabe wird jedoch nur am Ende einer Simulatorberechnung ausgewertet, so daß das tatsächliche Beenden des Programms, je nach Laufzeit des Simulators, erst einige Zeit nach Drücken der Taste stattfindet.
In der Unix-Version ist eine Tastatureingabe nach Verbannen des Optimierers in den Hintergrund und vorübergehenden Verlassens des Systems nicht mehr möglich. Daher wird dort statt der Tastatur das Vorhandensein eines Files namens ``stop'' im Arbeitsverzeichnis des Optimierers abgefragt, dessen Existenz als Abbruchbedingung interpretiert wird. Er kann über eine zusätzliche Kommandozeile z.B. durch den Befehl ``touch stop'' erzeugt werden. Hierbei ist aber darauf zu achten, daß die Datei im Arbeitsverzeichnis des Optimierers erzeugt werden muß.
Wird der Optimierer auf diese Weise geordnet verlassen, wird auch der Simulator automatisch beendet, und es werden noch verbliebene Übergabefiles entfernt, so daß Betriebs- und Dateisystem in einem gesäuberten Zustand hinterlassen werden.
Ganz eilige können natürlich auch Optimierer und Simulator jeweils per <Ctrl-C> einzeln abbrechen, müssen dann jedoch selbst für das Aufräumen im Dateisystem sorgen. Insbesondere führen nicht korrekt gelöschte Parameter- bzw.\ Rückgabedateien zu einem Versatz zwischen den zur Berechnung an den Simulator übergebenen Variablensätzen und den dazu zuzuordnenden Ergebnissen, die zu einer Störung des Systems führen. Außerdem kann bei erneutem Start der Optimierung eine versehentlich verbliebene Nachrichtendatei zum sofortigen Abbruch des Simulators führen.
Die Optimierungsergebnisse werden zur nachfolgenden Analyse in zwei Dateien festgehalten, die in Kap.~\ref{strateg.dat} erläutert werden.
\subsection{Steuerung durch die Variablen-Definitionsdatei CONDITIO.DAT}
\label{conditio}
Die Datei CONDITIO.DAT enthält die für die Definition des Optimierungsproblems wesentlichen Informationen über Zahl und Anfangswert der Variablen, sowie explizite Definitionsbereichsgrenzen.
\bf
Es ist sehr wichtig, daß die Einträge dieser Datei in der korrekten Reihenfolge und vollständig eingegeben werden. EPO Version~0.5 enthält keine automatische Überprüfung, ob die eingegebenen Daten korrekt eingetragen wurden.
\rm
Die Daten werden mit einfachen String- bzw.\ Zahlen-Einleseroutinen in C gelesen. Dementsprechend ist die Anzahl der Leerstellen zwischen den Einträgen unwichtig, genauso wie die Anzahl der Leerzeilen. In der vorliegenden Form des Optimierers erfolgt keine Validitätsprüfung. Das Optimierungsmodul gibt lediglich eine Statusmeldung über die eingelesenen Daten auf dem Bildschirm aus, an der der Benutzer die Eingabedaten-Interpretation überprüfen kann.
Ein typischer Dateiaufbau ist folgender (die Zeilennummerierung ist im Original wegzulassen und dient hier nur der Erklärung):
\begin{verbatim}
1: Example-1
2: Para_number 3
3: Name Value L.Limit U.Limit
4: Variable1 20 -1 50.45
5: Variable2 13.5 -5 25
6: Variable3 -4.3 -10 25.4
\end{verbatim}
Zeile 1 enthält den Namen des Optimierungsproblems (ein Wort ohne Leerzeichen). Er wird als ein Wort eingelesen und später in den Ausgabedateien als Kennzeichnung vermerkt.
Zeile 2 enthält das Kennwort ``Variablenzahl'' und die entsprechende Zahl (als Ganzzahl). Diese Anzahl von Zeilen wird eingelesen, nachdem in $\ldots$
Zeile 3 die Überschriften der entsprechenden Spalten als Erinnerungsstütze erwartet, aber überlesen werden.
Zeilen 4 bis 6 enthalten schließlich die Variablendefinitionen. In der ersten Spalte ist wiederum ein einzelnes Wort als Name einzutragen, in der zweiten Spalte der Anfangswert. Spalte 3 und 4 sind schließlich Unter- und Obergrenze der jeweiligen Variablen. Soll ein Definitionsbereich unbegrenzt sein, sind entsprechend große positive bzw.\ negative Zahlen einzugeben. (Bitte denken Sie daran, daß in der Shareware-Version maximal fünf Variable bearbeitet werden können. Sie können zwar weitere eintragen, doch werden sie nicht berücksichtigt.)
\subsection{Steuerung durch die Strategie-Definitionsdatei STRATEG.DAT}
\label{strateg.dat}
Die Datei STRATEG.DAT enthält die für die Ablaufsteuerung des Optimierungsmoduls wesentlichen Informationen über die Wahl des Simulators, Populationsgröße, Größe der Bestenliste, Art der Fortpflanzung, Wahl der Ergebnis- und Transferfiles, sowie zwei weitere Strategieparameter, die weiter unten noch besprochen werden.
\bf
Es ist sehr wichtig, daß die Einträge in der korrekten Reihenfolge und vollständig eingegeben werden. EPO Version~0.5 enthält keine automatische Überprüfung, ob die eingegebenen Daten korrekt eingetragen wurden.
\rm
Die Daten werden mit einfachen String- bzw.\ Zahlen-Einleseroutinen in C gelesen. Dementsprechend ist die Anzahl der Leerstellen zwischen den Einträgen unwichtig, genauso wie die Anzahl der Leerzeilen. Eine Validitätsprüfung der eingelesenen Daten findet in EPO Version~0.5 nicht statt. Das Optimierungsmodul gibt lediglich eine Statusmeldung über die eingelesenen Daten auf dem Bildschirm aus, an der der Benutzer die Eingabedaten-Interpretation überprüfen kann.
Ein typischer Dateiaufbau ist folgender (die Zeilennumerierung ist im Original wegzulassen und dienen hier nur der Erklärung):
\begin{verbatim}
1: EPO-0.5
2: minimize
3: simulator_name simu
4: optidelay 400
5: individual_number 30
6: best 5
7: inbreeding 1
8: display 5
9: result_file Erg1.out
10: history_file Gra1.out
11: transfer_dir g:\
12: tau0 0.3
13: tau1 2
14: init_var 0.1
15: auto_stop 300
\end{verbatim}
Zeile 1 enthält das Wort EPO-0.5 als Kennung, daß es sich um eine Strategieparameterdatei zur richtigen Version von EPO handelt.
In Zeile 2 können die Schlüsselwörter ``maximize'' oder ``minimize'' eingetragen werden. Entsprechend wird im Optimierungslauf nach maximalem oder minimalem Wert sortiert.
In Zeile 3 wird der gewünschte Simulator angegeben, der automatisch vom Optimierer aus gestartet wird. Der Name muß so eingetragen werden, wie er als Programmstart-Aufruf in einer Kommandozeile geschrieben werden müßte. Da üblicherweise der Simulator im gleichen Verzeichnis wie der Optimierer liegt, reduziert sich in diesem Fall der Eintrag schlicht auf den Namen des Simulators ohne zusätzliche Pfadangaben.
Der Eintrag in Zeile 4 definiert die Pause, die der Optimierer nach einem erfolglosen Leseversuch des Nachrichtenfiles vom Simulator einlegt. Die Angabe erfolgt in Millisekunden%
\footnote{In der Unix-Version steht typischerweise kein Millisekunden-Timer zur Verfügung, sondern ein Sekunden-Timer. Daher wird in dort die Millisekundenangabe in eine Sekundenangabe umgesetzt: z.B. 2340~ms $\rightarrow$ 2~s).}. %
Insbesondere bei langlaufenden Simulatorprogrammen ist es verschwendete (Rechen-)Zeit, den Optimierer pausenlos nachschauen zu lassen. Selbst bei kurzlaufenden Simulatorprozessen ist eine Wartezeit von ca. 0.5~s sinnvoll.
In Zeile 5 wird nach dem Kennwort die Anzahl der Individuen in der Population eingetragen; Zeile 6 enthält die Angabe der Anzahl bester Individuen, die als Elternpopulation in die nächste Generation übernommen werden. Im vorliegenden Beispiel werden also pro Generation die fünf besten Individuen übernommen und weitere 25 Individuen neu erzeugt.
In Zeile 7 wird angegeben, ob Nachkommen ausschließlich aus einer Rekombination zweier unterschiedlicher Individuen entstehen dürfen (inbreeding 0) oder auch durch die (zufällige) Wahl des selben Individuum, somit durch reine Mutation (inbreeding 1) gebildet werden können.
In Zeile 8 wird die Anzahl der pro Generation darzustellenden Bestenzahl eingetragen. Würde die angezeigte Individuenzahl immer gleich der Größe der Bestenliste gesetzt, könnte bei einer umfangreichen Bestenliste und einem kleinen Anzeigefenster gerade der interessierende Kopfbereich beim Anzeigen zu schnell aus dem Blickfeld verschwinden. Der Eintrag einer kleinen Zahl in dieser Zeile verhindert dies.
Zeile 9 enthält den Dateinamen, in den die jeweils beste Parameterkonstellation, sozusagen als Denkmal, abgelegt wird. Der Eintrag wird als komplette Pfadangabe verstanden und kann daher auch eine explizite Laufwerksangabe beinhalten.
Zeile 10 enthält den Namen der Datei, an die jeweils bei einer absoluten Verbesserung eine Zeile mit Nummer der Generation und dem Bestwert der Zielfunktion angehängt wird. Er wird wie der Eintrag in Zeile 9 interpretiert. Hiermit ist im Nachhinein der Optimierungsfortschritt im Laufe der Generationen nachzuvollziehen.
Zeile 11 gibt das Verzeichnis an, in dem die zwischen dem Simulator und dem Optimierer ausgetauschten Transferfiles abgelegt werden. Steht eine RAM-Disk im System zur Verfügung, kann diese sinnvollerweise hierzu eingesetzt werden --- die Transfergeschwindigkeit wird so maximiert, die Festplattenaktivität minimiert. Die eingetragene Zeichenkette wird den Dateinamen der Transferfiles vorangestellt und ist dementsprechend zu wählen.
Zeilen 12 und 13 enthalten zwei Steuerparameter, die für ein Fein-Tuning des Optimierungsfortschritts eingesetzt werden können. Werte für beide Parameter $tau0$ und $tau1$ zwischen 0.2 und 2.0 sind generell empfehlenswert. Bei wiederholtem Durchrechnen gleichermaßen gestalteter Optimierungsprobleme kann durch Variation eine gewisse Konvergenzbeschleunigung erreicht werden, allerdings unter Umständen auf Kosten der Konvergenzsicherheit bei multimodalen Problemen.
In Zeile 14 wird die anfängliche Variationsbandbreite der neu zu erstellenden Population angegeben. Der hier einzutragende Wert ist als als relative Abweichung gegenüber den Anfangswerten der Variablen, definiert in CONDITIO.DAT (siehe Abschnitt~\ref{conditio}), zu verstehen. Es ist nur eine globale Angabe möglich, die für alle Variablen gleichermaßen gilt.
Zeile 15 enthält schließlich eine Angabe über die maximale Anzahl von Generationen, in denen nacheinander keine Verbesserung erreicht wurde. Wird diese Zahl überschritten, beendet der Optimierer seine Arbeit und stoppt auch den Simulator.
\section{Erste Versuche mit beigelegten Beispielproblemen}
Einen ersten Einstieg in die Funktionsweise von EPO erhalten Sie mit den beigelegten Beispielproblemen:
\item Bennenen Sie alle Dateien mit der Endung BIN in solche gleichen Namens, aber mit der Endung EXE um. (Also z.B.: \verb+ren shopti.bin shopti.exe+)
\item Schauen Sie Sich die Dateien CONDITIO.DAT und STRATEG.DAT an. Versuchen Sie, anhand der obigen Erläuterungen die Einträge zu verstehen. In den Beispieldateien werden drei Variablen mit relativ begrenzten Definitionsbereichen behandelt. Als Übergabe-Verzeichnis dient das aktuelle Arbeitsverzeichnis. Als Simulator ist SIMU(.EXE) voreingestellt.
\item Starten Sie den Optimierer SHOPTI.EXE.
\item Beobachten Sie dessen Ausgabefenster: Nach der Einschaltmeldung werden die eingelesenen, zu bearbeitenden Variablen zur Kontrolle angezeigt.
\item Zunächst wird eine erste Elterngeneration gebildet, erkennbar an der entsprechenden Kontrollausgabe.
\item Dann beginnt die sich immer wiederholende Schleife: Erzeugung neuer Individuen, Verschicken an den Simulator, Rücknahme der Ergebnisse, Sortierung der Individuen nach Zielfunktionswert, ggf.\ Schreiben neuer Ergebnisdateien, Anzeige des momentanen Optimierungsstandes.
\item Brechen Sie den Programmlauf wahlweise durch Eingabe von ``q'' ab oder warten Sie, bis die angegebene Zahl von Generationen (im Beispiel: fünf) keine weitere Verbesserung mehr erreicht wurde und der Optimierer von selbst stoppt.
\item Schauen Sie Sich die Ergebnisdatei (im Beispiel: ERG1.OUT) an, um die beste gefundene Einstellung der Variablen abzufragen. In der Historiendatei (im Beispiel: GRA1.OUT) können Sie die Entwicklung des Zielfunktionswertes nachvollziehen: Bei jeder absoluten Verbesserung wird jeweils eine Eintragszeile hinzugeschrieben, in der Generation und Wert notiert werden. Durch einen Datenplotter (z.B. GnuPlot) kann diese Datei sehr einfach in eine graphische Darstellung des Optimierungsfortschrittes umgesetzt werden.
\item {\bf Zweites Beispiel: Aufruf eines externen Simulators --- Gaußfit}
\item Ändern Sie in der Datei STRATEG.DAT den Eintrag ``simu'' in ``trans'' um.
\item Ändern Sie dort auch die Einträge ERG1.OUT und GRA1.OUT in Ihnen genehme Dateinamen um (sonst werden die alten Dateien überschrieben bzw.\ verlängert).
\item Starten Sie erneut den Optimierer.
\item Holen Sie das Fenster von TRANS.EXE nach vorne und beobachten Sie die von GAUSSFIT im Fenster von TRANS erzeugten Kontrollausgaben (eingelesene Meßwerte, dazu berechnete Gaußglockenwerte entsprechend den Übergabeparametern, Fehlerquadratsumme, schließlich bezogene Fehlerquadratsumme als Rückgabewert.)
\item Beobachten Sie wieder die Entwicklung des Optimierungserfolges im SHOPTI-Fenster und brechen Sie den Lauf nach Wunsch ab.
\end{itemize}
Beim regulären Abbruch des Programmlaufs (durch ``q'' oder Erreichen der Abbruchbedingung) wird eine weitere Datei erzeugt: STATUS.ERG. Sie ist strukturell gleich der Ergebnisdatei, enthält aber den bei Abbruch vorliegenden Stand der Population. Sie kann gelegentlich für einen Vergleich mit den absoluten Bestwerten herangezogen werden.
\section{Aus der Praxis: Anpassung an ``echte'' Problemstellungen}
\label{Praxis}
Die Anwendung von EPO auf reale Problemstellungen erfordert prinzipiell einen geringen Programmieraufwand. Um diesen zu minimieren, habe ich die beiden Schablonen SIMU.C und TRANS.C beigelegt, die bereits die Interaktion von Simulator und Optimierer übernehmen und beispielhaft den Aufruf eines externen, komplett eigenständigen Simulators übernehmen.
Alle Programmteile wurden mit dem EMX-System von E. Mattes erstellt und auf Funktionstüchtigkeit überprüft. Dies nicht zuletzt, weil der zugrundeliegende C-Compiler mittlerweile zu einem Standardcompiler in der Unix-Welt avanciert ist und somit eine gute Grundlage zur Portierung auf andere Plattformen darstellt.
Natürlich können auch andere Compilersysteme verwendet werden, nur sind dann ggf.\ die INCLUDE-Dateien einer anderen Bibliotheksstruktur anzupassen. Ich habe mich aber bemüht, nach Möglichkeit nur einfachste Grundoperationen zu verwenden, die in allen Systemen zur Verfügung stehen sollten.
Beim Gnu-C-Compiler (Sparc) und dem EMX-System (OS/2) ist beim Linken des Simulators eine explizite Angabe der Mathe-Bibliothek erforderlich. Schauen Sie ggf.\ in den zugehörigen Handbüchern nach!
\subsection{Direkte Programmierung eines Simulators}
Bei erforderlicher Neuprogrammierung eines Simulators kann SIMU.C als Basis verwendet werden und übernimmt die gesamte Kommunikation mit dem Optimierer. Der neu zu programierende Simulatorkern ersetzt dann das Beispielproblem im Unterprogramm \verb+rechne()+.
Die Anzahl der zu bearbeitenden Parameter steht in der Variablen \verb+Parazahl+ zur Verfügung.
Die aktuellen Variablenwerte werden im der Struktur \verb+Indi+ als \verb+Indi.koeff[i]+ zur Verfügung gestellt. Das Simulatorergebnis ist bei Verlassen von \verb+rechne()+ in der Variablen \verb+Indi.Ergebnis+ zum Rückversand an den Optimierer bereitzustellen.
Auch die weiteren Einträge von \verb+Indi+ werden durch die Informationen aus dem Optimierer initialisiert, doch sind diese teilweise historisch bedingt bzw.\ werden in einer kommenden Version verwendet werden, die echtes Multi-Processing auf verschiedenen PCs gleichzeitig unterstützen wird. Daher bitte diese Einträge nicht benutzen, aber auch nicht ändern, da sie an den Optimierer zurückgegeben werden.
Falls erforderlich, stehen die Variablennamen über \verb+Limits[i].Name+ zur Verfügung; die restlichen Einträge in diesem Feld sind nicht initialisiert!
\subsection{Anbindung eines externen Simulators über beigelegtes Hilfsprogramm}
Steht bereits ein eigenständiger Simulator für das zu optimierende System zur Verfügung, kann TRANS.C als Basis für die Transferabwicklung zwischen Optimierer und Simulator verwendet werden. Auch hier ist die Kommunikation zwischen TRANS und SHOPTI bereits fertig implementiert, so daß nur der Aufrufteil für den externen Simulator nachbearbeitet werden muß. Dies ist im Unterprogramm \verb+rufe()+ zu erledigen.
Die Bereitstellung der jeweils aktuellen Variablendaten erfolgt mit den gleichen Datenstrukturen und unter den gleichen Bedingungen wie im Programm SIMU.C, daher bitte dort das Procedere nachlesen.
\section{Fehlersuche}
Wegen der geringen Fehlertoleranz der Einleseroutinen von EPO sind durchaus Laufzeitfehler möglich, die einen Optimierungslauf stören oder unmöglich machen. Da jedoch alle Schnittstellen zwischen den Programmodulen als ASCII-Textdateien ausgeführt sind, ist eine Fehleranalyse anhand der jeweiligen Einträge möglich.
Insbesondere empfiehlt es sich in einem solchen Fall, die Programme nach Bereitstellung der erforderlichen Datenfiles jeweils einzeln zu starten, um deren Verhalten und deren Antwortfile-Generierung beobachten zu können. Bei SHOPTI ist ein Einzelstart nicht ohne weiteres möglich, da es ja automatisch den Simulator aufruft. Hier hilft es, einen nicht-existenten Namen als Simulatorbezeichnung in die STRATEG.DAT einzutragen. SHOPTI gibt dann beim mißlungenen Startversuch des Simulators einen Fehler an, der aber auf den weiteren Ablauf keine Auswirkungen hat. Auf diese Weise endet die Arbeit von SHOPTI nach Schreiben der Übergabefiles, da keine Rückmeldung erfolgen kann. Das Programm kann nun abgebrochen werden.
Die folgende Übersicht gibt an, welche Dateien bei Start eines Einzelprogramms vorhanden sein müssen, welche erzeugt werden und welche einen normalen Programmlauf evtl.\ stören können:
\vspace{1cm}
\begin{tabular}{|llll|}
\hline
Programm im Test & notwendig & erzeugt & störend \\
TRANS & STRATEG.DAT & S2O.DAT & (falsches O2S.DAT) \\
& O2S.MSG & S2O.MSG &\\
& O2S.DAT & & \\
& & & (Ausgabefile)\\
\hline
\end{tabular}
\vspace{1cm}
Bei SHOPTI werden die eingeklammerten Dateien nicht notwendigerweise erzeugt, bei SIMU und TRANS können falsche Einträge in der O2S.DAT zu sofortigem Abbruch führen. In dem Fall ist zu prüfen, ob als zu bearbeitende Parameterzahl eine ``0'' angegeben ist, was einem Ende-Befehl für das Simulator/Transferprogramm bedeutet.
Vorsicht bei der Einbindung eines externen Simulators über TRANS: Systembedingt kann ein vom externen Simulator an TRANS zurückgelieferter Datenfile nicht automatisch vom Optimierer mit aufgeräumt/entfernt werden, weil ihm hierzu keine Informationen vorliegen! Entweder muß der Anwender dies in TRANS an der entsprechenden Stelle einbauen (dort, wo die Abfrage auf gewünschten Programmabbruch stattfindet) oder aber nach Beenden eines Optimierungslaufs die fragliche Datei von Hand löschen.
Geschieht dies nicht, ergibt sich ein Versatz zwischen der dem externen Simulator zur Durchrechnung übergebenen Parametereinstellung und dem von TRANS eingelesenen Rückgabewert, der die Interpretierbarkeit des Ergebnisses zerstört. Dieses Problem ist generell nicht umgehbar, da --- im Gegensatz zum Datenaustausch zwischen TRANS und SHOPTI --- kein zusätzlicher Nachrichtenfile die Synchronisierung der Parameterübergabe übernimmt.
Der Aufbau der zwischen SHOPTI und SIMU/TRANS ausgetauschten Datenfiles ist selbsterklärend und braucht hier nicht weiter diskutiert zu werden.
\section{Versions-Logbuch und Ausblick}
Die Version 0.1 wurde im März 1994 zunächst nur lokal in einer Mailbox veröffentlicht und fast unmittelbar durch die Version 0.2 ersetzt.
Ergänzungen und Korrekturen in EPO 0.2:
\begin{itemize}
\item Übergabeproblem zwischen Optimierer und Simulator (temporäre Inkonsistenz des Filesystems) wurde durch Überprüfung der Anzahl korrekt gelesener Einträge beseitigt.
\item Erforderliche Wartezeit bis zur Konsistenz des Filesystems wird kontinuierlich adaptiv auf Minimalwert angepaßt.
\item Es wurde eine in STRATEG.DAT definierbare Abfrage-Wartezeit für den Optimierer eingeführt, die ein unnötiges, rechenzeitverbrauchendes Pollen im Filesystem verhindert.
\item Einige kleinere Inkonsistenzen beim Schreiben der Ergebnisfiles wurden entfernt.
\item Bei Verlassen des Optimierers durch eine normale Abbruchbedingung wird ein weiterer Ergebnisfile namens STATUS.ERG erzeugt, der den momentanen Stand dokumentiert, auch wenn er nicht der absolute Beststand ist.
\end{itemize}
EPO 0.3 und 0.4 waren interne Versionen.
Ergänzungen und Korrekturen in EPO 0.5:
\begin{itemize}
\item Festlegung der anfänglichen Variationsbandbreite über die Definitionsbereichsgrenzen wurde durch eine benutzerdefinierbare Anfangs-Spannweitenangabe ersetzt, um eine Wiederaufnahme eines schon erfolgreichen Optimierungslaufes zu ermöglichen.
\item Implementation der Unix-Version auf der Sparc-Platform
\item Automatisches Entfernen des ``Stop''-Files in der Unix-Version.
\item Verschönerung (sic!) der Kontrollausgaben.
\end{itemize}
\bigskip
Die vorliegende Version 0.5 stellt eine sinnvoll lauffähige und schon in der Praxis einsetzbare Vorversion von EPO~1.0 dar. Ich wollte diese wiederum so schnell wie möglich herausgeben, um so schnell wie möglich von Anwendern Rückmeldungen für die Weiterentwicklung des Systems zu bekommen.
Wesentlicher Problempunkt dürfte momentan die unfexible Eingabedaten-Einleseroutine sein, die eine sehr spezielle Formatierung und eine strenge Beachtung von Reihenfolge und Form der Eingabedaten erfordert. Hier soll ein fehlertoleranteres System eingebaut werden.
Als nächstes ist eine automatische graphische Ausgabe des aktuellen Optimierungsstandes und der Historie des Vorgangs über das Programm GNUPLOT geplant, für das zur Zeit eine Ausgabeschnittstelle in den Optimierer eingebaut wird.
Des weiteren ist eine Umstellung der Informationsübergabe von Datenfiles auf die Verwendung von RAM-internen Pipes geplant, um den Kommunikations-Overhead so gering wie möglich zu halten.
Insbesondere bei langen Simulatorläufen wäre es sinnvoll, mehrere Simulatoren parallel auf mehreren Maschinen laufen lassen zu können. Auch das ist in einer zukünftigen Version von EPO vorgesehen.
Schließlich ist soll das Mensch-Maschine-Interface verbessert werden, das in der vorliegenden Version zugegebenermaßen eher steinzeitlich anmutet. Doch steht dieser Punkt bewußt ganz hinten auf der Liste, weil mir die Funktion wichtiger ist als das Aussehen und der Programmlauf sowieso am sinnvollsten als Hintergrundprozeß und damit ohne große Benutzer-Interaktion stattfindet.
\section{Registrierungsmodalitäten für Vollversion}
So, nun kommt der unangenehmste Teil der Benutzungseinführung, nämlich der, in dem es um Geld geht. Ich hoffe aber, diesen so angenehm wie möglich gestaltet zu haben $\ldots$
Wie bei Shareware üblich, darf dieses Paket frei kopiert und weitergegeben werden, unter der Voraussetzung, daß keinerlei Änderungen daran gemacht werden. Die vorliegende, eingeschränkt nutzbare Version (bis zu fünf zu optimierende Parameter) darf beliebig lange ohne Entrichtung von Nutzungsgebühren eingesetzt werden. Werden mit EPO praktisch nutzbare Ergebnisse erzielt, erwarte ich bei einer Veröffentlichung solcher Ergebnisse eine explizite Erwähnung von EPO als eingesetztes Hilfsmittel. Darüber hinaus bin ich natürlich auch einer freiwilligen finanziellen Anerkennung meiner Programmierleistung nicht abgeneigt.
Eine uneingeschränkt nutzbare Version mit bis zu mehreren hundert Variablen, die insbesondere auch eine Bearbeitung von Reihenfolgeproblemen und gemischt reellwertigen + diskreten Aufgabenstellungen erlaubt, steht sowohl für OS/2- wie auch für Unix-Systeme zur Verfügung und ist direkt bei der Programmautorin zu erwerben. Der Preis richtet sich nach dem Umfang der zu bewältigenden Aufgabenstellungen und liegt typischerweise zwischen 200,--~DM und 2.000,--~DM.
Bei manchen komplexeren Optimierungsproblemen wird die vorliegende Programmstruktur nicht einsetzbar sein, obwohl eine evolutionsstrategische Vorgehensweise angeraten wäre. In diesen Fällen besteht die Möglichkeit, spezialisierte Programmversionen zu erstellen, die genau die Anforderungen erfüllen. Hierzu bitte die Programmautorin direkt ansprechen!
\section*{Danksagung}
An dieser Stelle möchte ich es nicht versäumen, meinem Bruder Dr.\ Peter Roosen für die Überlassung der ersten Internversionen des Evolutionären Optimierers zu danken, auf dem diese Version aufbaut. Ich hoffe, mit der Überarbeitung dieser Quelle für OS/2-PCs und Unix-Workstations zu einer weiteren Verbreitung der Idee naturanaloger Optimierungsverfahren beizutragen und ihm ein Feed-Back für die systematisierte Entwicklung und Anwendung im Bereich der Verfahrenstechnik zu geben.
Ein großes Dankeschön auch an Eberhard Mattes, der mir mit seinem EMX-C-Compilersystem die Möglichkeit gab, dieses Programmsystem unter OS/2 zu realisieren. Hätte ich einige hundert DM für einen kommerziellen Compiler ausgeben müssen, wäre es wohl nicht entstanden.
\bibitem{ Muelle:EvoBeisp} K.D.\ Müller: Optimieren mit der Evolutionsstrategie in der Industrie anhand von Beispielen; Diss. TU Berlin, 1986
\bibitem{ Otto:SimAn} T. Otto: Reiselust --- Travelling Salesman, eine neue Strategie für eine alte Aufgabe; c't, 1(1994)188--194
\bibitem{ Poeppl:Funktional} J.\ Pöpplau: Funktionalminimierung mit Evolutionsstrategien unter Verwendung von finite Elemente Diskretisierungen; Mitteilung aus dem Institut für Strömungslehre und Strömungsmaschinen, Hochschule der Bundeswehr Hamburg, Heft Juli 1982
\bibitem{ Rechen:Evolut} I.\ Rechenberg: Evolutionsstrategie; Frommann-Holzboog, ISBN 3-7728-0-374
\bibitem{ Rechen:EvoDarw} I.\ Rechenberg: The evolution strategy. A mathematical model of Darwinian evolution; Berlin 1984
\bibitem{ Rechen:EvoStrat} I.\ Rechenberg: Evolution strategy: Nature's way of optimization; Lecture notes in Engineering, Vol. 47, Springer,
Berlin 1989
\bibitem{ Rieck:ModellNatur} C. Rieck: Modell Natur --- Naturanaloge Verfahren in der Computersimulation; c't, 11(1993)201--208
\bibitem{ Riedel:Galvanik} H.J.\ Riedel: Einsatz rechnergestützter Optimierung mittels der Evolutionsstrategie zur Lösung galvanotechischer Probleme; Dissertation TU Berlin, 1984
\bibitem{ Handelsreis} G.\ Rudolph: Global Optimization by Means of
Distributed Evolution Strategies; in H.-P.\ Schwefel und R.\ Männer (Hrsg.):
Parallel Problem Solving from Nature, Lecture Notes in Computer Science 496,
S.\ 209--213, Springer Verlag, 1991
\bibitem{ Schmie:Mikrowelle} H.\ Schmiedel: Anwendung der Evolutionsoptimierung bei Mikrowellenschaltungen; Frequenz 35(1981)306-310
\bibitem{ Schwef:Opti} H.-P.\ Schwefel: Numerische Optimierungs von Computermodellen mittels der Evolutionsstrategie; Interdisciplinary Systems Research 26, Birkhäuser 1977
\bibitem{ Schwef:DirectSearch} H.-P.\ Schwefel: Direct Search for Optimal Parameters within Simulation Models; Proc.\ of the 12$^{\rm th}$ Annual Simulation Symposium, Tampa, Florida, 1979
\bibitem{ Schw88} H.-P.\ Schwefel: Evolutionary Learning Optimum-Seeking on
Parallel Computer Architectures; in A.\ Sydow, S.G.\ Tzafestas, R.\
Vichnevetsky (Hrsg.): Proceedings of the International Symposium on Systems
Analysis and Simulation 1988, I: Theory and Foundations, S.\ 217--225,
Akademie-Verlag, Berlin, September 1988
\bibitem{ PPSN:1990} H.-P.\ Schwefel und R.\ Männer (Hrsg.): International
Conference on ``Parallel Problem Solving from Nature'', Dortmund 1990;
Lecture Notes in Computer Science 496, Springer Verlag, 1991
